import org.junit.Test;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Solution {
    //剑指 Offer 31. 栈的压入、弹出序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length==0&&popped.length==0){
            return true;
        }
        if(pushed.length==0||popped.length==0){
            return false;
        }
        int left=0;
        int right=0;
        Stack<Integer> stack=new Stack<>();
        while(left<pushed.length&&right<popped.length){
            if(pushed[left]!=popped[right]){
                stack.push(pushed[left]);
                left++;
            }else{
                right++;
                left++;
                while(!stack.empty()){
                    if(stack.peek()==popped[right]){
                        stack.pop();
                        right++;
                    }else{
                        break;
                    }
                }
            }
        }
        while(!stack.empty()){
            if(stack.pop()!=popped[right++]){
                return false;
            }
        }
        if(stack.empty()&&right>=popped.length){
            return true;
        }
        return false;
    }
    //从左到右依次打印二叉树
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int [0];
        }
        Queue<TreeNode> queue=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            list.add(cur.val);
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        int [] arr=new int[list.size()];
        for(int i=0;i<list.size();i++){
            arr[i]=list.get(i);
        }
        return arr;
    }
    public int[] spiralOrder(int[][] matrix) {
        //判断matrix是不是为空
        if(matrix[0].length==0){
            return new int[1];
        }
        int left=0;
        int right=matrix[0].length-1;
        int up=0;
        int down =matrix.length-1;
        int len=(right+1)*(down+1);
        int [] arr1=new int[len];
        int count=0;
        while(left<=right&&up<=down){
            //打印上边界
            for(int i=left;i<=right;i++){
                arr1[count]=matrix[up][i];
                count++;
            }
            up++;
            if(up>down){
                break;
            }
            //打印右边界
            for(int i=up;i<=down;i++){
                arr1[count]=matrix[i][right];
                count++;
            }
            right--;
            if(left>right){
                break;
            }
            //打印下边界
            for(int i=right;i>=left;i--){
                arr1[count]=matrix[down][i];
                count++;
            }
            down--;
            if(up>down){
                break;
            }
            //打印左边界
            for(int i=down;i>=up;i--){
                arr1[count]=matrix[i][left];
                count++;
            }
            left++;
            if(left>right){
                break;
            }
        }
        return arr1;
    }
    class  TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public static  TreeNode root;
    //二叉树的镜像
    public  TreeNode mirrorTree(TreeNode root){
        if(root==null){
            return  null;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode node=stack.pop();
            if(node.left!=null){
               stack.add(node.left);
            }
            if(node.right!=null){
                stack.add(node.right);
            }
            TreeNode cur=node.left;
            node.left=node.right;
            node.right=cur;
        }
        return  root;
    }
    public TreeNode mirrorTree1(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=mirrorTree1(root.right);
        root.right=mirrorTree1(tmp);
        return root;
    }
}